class Solution
{
public:
    Node* copyRandomList(Node* head)
    {
        map<Node*, Node*> p;
        Node* cur = head;
        while (cur)
        {
            p[cur] = new Node(cur->val);
            cur = cur->next;
        }
        cur = head;
        while (cur)
        {
            p[cur]->random = p[cur->random];
            cur = cur->next;
        }
        cur = head;
        while (cur)
        {
            p[cur]->next = p[cur->next];
            cur = cur->next;
        }
        return p[head];
    }
};